package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class _103_zigzagLevelOrder {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){return res;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int level = 1;
        while (!queue.isEmpty()){
            //每轮循环遍历处理一层节点
            boolean fromRight = level%2==0;
            int size = queue.size();
            List<Integer> listLevel = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode curr = queue.poll();

                if(fromRight){
                    listLevel.add(0, curr.val);
                }else {
                    listLevel.add(curr.val);
                }
                if(curr.left!=null){queue.add(curr.left);}
                if(curr.right!=null){queue.add(curr.right);}
            }
            res.add(listLevel);
            level++;
        }
        return res;
    }

    //DFS 前序遍历
    public List<List<Integer>> zigzagLevelOrder1(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        preOrder(root, 0, res);
        return res;
    }
    private void preOrder(TreeNode node, int currLevel, List<List<Integer>> res){
        if(node==null){return;}
        //处理当前遍历
        if(res.size()==currLevel){
            List<Integer> levelNode = new ArrayList<>();
            res.add(levelNode);
        }
        List<Integer> levelNodes = res.get(currLevel);
        if(currLevel%2==0){levelNodes.add(node.val);}
        else {levelNodes.add(0, node.val);}

        preOrder(node.left, currLevel+1, res);
        preOrder(node.right, currLevel+1, res);
    }

}
